// 493. 翻转对

/**
 * 。。。。。归并排序 树状数组 总是成对出现
 */

function reversePairs(nums: number[]): number {
    return mergeSortCnt(nums,0,nums.length-1)
};

//归并排序解法
function mergeSortCnt(nums:number[],l:number,r:number):number{
    if(l>=r) return 0
    const mid = Math.floor((l+r)/2)
    let n_l = mergeSortCnt(nums,l,mid)
    let n_r = mergeSortCnt(nums,mid+1,r)

    let n = n_l+n_r

    //双指针统计
    let i = l
    let j = mid+1
    while(i<mid+1&&j<r+1){
       if(nums[i]<=2*nums[j]) i++
       else{
           n+=(mid+1-i)
           j++
       }
    }
    i = l
    j = mid+1
    
    //合并两个数组
    const temp_nums:number[] = []
    while(i<mid+1&&j<r+1){
        if(nums[i]<=nums[j]){
            temp_nums.push(nums[i])
            i++
        }else{
            temp_nums.push(nums[j])
            j++
        }
    }
    if(i<mid+1){
        temp_nums.push(...nums.slice(i,mid+1))
    }else if(j<r+1){
        temp_nums.push(...nums.slice(j,r+1))
    }
    nums.splice(l,r-l+1,...temp_nums)
    return n
}
